{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #弹珠游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ballGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #弹珠游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。\n",
    "\n",
    "`N*M` 大小的弹珠盘的初始状态信息记录于一维字符串型数组 `plate` 中，数组中的每个元素为仅由 `\"O\"`、`\"W\"`、`\"E\"`、`\".\"` 组成的字符串。其中：\n",
    "- `\"O\"` 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；\n",
    "- `\"W\"` 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）；\n",
    "- `\"E\"` 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）；\n",
    "- `\".\"` 表示空白区域（弹珠可通行）。\n",
    "\n",
    "游戏规则要求仅能在边缘位置的 **空白区域** 处（弹珠盘的四角除外）沿 **与边缘垂直** 的方向打入弹珠，并且打入后的每颗弹珠最多能 **前进** `num` 步。请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 **按任意顺序** 返回答案。\n",
    "\n",
    "**注意：**\n",
    "- 若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。\n",
    "\n",
    "**示例 1：**\n",
    "> 输入\b：\n",
    ">`num = 4`\n",
    ">`plate = [\"..E.\",\".EOW\",\"..W.\"]`\n",
    "> \n",
    "> 输出：`[[2,1]]`\n",
    "> \n",
    "> 解释：\n",
    "> 在 `[2,1]` 处打入弹珠，弹珠前进 1 步后遇到转向器，前进方向顺时针旋转 90 度，再前进 1 步进入洞中。\n",
    "![b054955158a99167b8d51da0e22a54da.gif](https://pic.leetcode-cn.com/1630392649-BoQncz-b054955158a99167b8d51da0e22a54da.gif){:width=\"300px\"}\n",
    "\n",
    "**示例 2：**\n",
    "> 输入\b：\n",
    ">`num = 5`\n",
    ">`plate = [\".....\",\"..E..\",\".WO..\",\".....\"]`\n",
    "> \n",
    "> 输出：`[[0,1],[1,0],[2,4],[3,2]]`\n",
    "> \n",
    "> 解释：\n",
    "> 在 `[0,1]` 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向逆时针旋转 90 度，再前进 1 步进入洞中。\n",
    "> 在 `[1,0]` 处打入弹珠，弹珠前进 2 步，遇到转向器后前进方向顺时针旋转 90 度，再前进 1 步进入洞中。\n",
    "> 在 `[2,4]` 处打入弹珠，弹珠前进 2 步后进入洞中。\n",
    "> 在 `[3,2]` 处打入弹珠，弹珠前进 1 步后进入洞中。\n",
    "![b44e9963239ae368badf3d00b7563087.gif](https://pic.leetcode-cn.com/1630392625-rckbdy-b44e9963239ae368badf3d00b7563087.gif){:width=\"350px\"}\n",
    "\n",
    "\n",
    "**示例 3：**\n",
    "> 输入\b：\n",
    ">`num = 3`\n",
    ">`plate = [\".....\",\"....O\",\"....O\",\".....\"]`\n",
    "> \n",
    "> 输出：`[]`\n",
    "> \n",
    "> 解释：\n",
    "> 由于弹珠被击中后只能前进 3 步，且不能在弹珠洞和弹珠盘四角打入弹珠，故不存在能让弹珠入洞的打入位置。\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= num <= 10^6`\n",
    "- `1 <= plate.length, plate[i].length <= 1000`\n",
    "- `plate[i][j]` 仅包含 `\"O\"`、`\"W\"`、`\"E\"`、`\".\"` "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [EXvqDp](https://leetcode.cn/problems/EXvqDp/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [EXvqDp](https://leetcode.cn/problems/EXvqDp/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[\"..E.\",\".EOW\",\"..W.\"]', '5\\n[\".....\",\"..E..\",\".WO..\",\".....\"]', '3\\n[\".....\",\"....O\",\"....O\",\".....\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "class Solution:\n",
    "\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "\n",
    "            left = num\n",
    "\n",
    "            while plate[x][y] != 'O':\n",
    "\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "\n",
    "                x += DIRS[d][0]\n",
    "\n",
    "                y += DIRS[d][1]\n",
    "\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "\n",
    "                left -= 1\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for j in range(1, n - 1):\n",
    "\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "\n",
    "        for i in range(1, m - 1):\n",
    "\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = ((0,1),(1,0),(0,-1),(-1,0))\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        row , column = len(plate) , len(plate[0])\n",
    "        ans = []\n",
    "        def check(x,y):\n",
    "            if(plate[x][y]!=\".\"):\n",
    "                return False\n",
    "            num1 = num\n",
    "            d = -1\n",
    "            if(y==0):\n",
    "                d = 0\n",
    "            if(y==column-1):\n",
    "                d = 2\n",
    "            if(x==0):\n",
    "                d = 1\n",
    "            if(x==row-1):\n",
    "                d = 3\n",
    "            while(plate[x][y]!='O'):\n",
    "                x+=direction[d][0]\n",
    "                y+=direction[d][1]\n",
    "                if(x<0 or x>=row or y<0 or y>=column):\n",
    "                    return False\n",
    "                if(plate[x][y]=='E'):\n",
    "                    d=(d+1)%4\n",
    "                if(plate[x][y]=='W'):\n",
    "                    d=(d+3)%4\n",
    "                num1 -= 1\n",
    "                if(num1<0):\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(1,row-1):\n",
    "            if check(i,0):\n",
    "                ans.append([i,0])\n",
    "            if check(i,column-1):\n",
    "                ans.append([i,column-1])\n",
    "        for j in range(1,column-1):\n",
    "            if check(0,j):\n",
    "                ans.append([0,j])\n",
    "            if check(row-1,j):\n",
    "                ans.append([row-1,j])\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0) ] # 右下左上（顺时针）\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x <= m-1 and 0 <= y <= n-1):\n",
    "                    return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        # 0：向右，1：向下，2：向左，3：向上\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  \n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  \n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        def check(x, y,d):\n",
    "            left = num\n",
    "            while plate[x][y] != \"O\":\n",
    "                if left == 0:\n",
    "                    return False\n",
    "                if plate[x][y] == \"W\":\n",
    "                    d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == \"E\":\n",
    "                    d = (d + 1) % 4  # 顺时针\n",
    "                x += dir[d][0]\n",
    "                y += dir[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n):\n",
    "                    return False\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        dir = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        ans = list()\n",
    "        for i in range(1,n-1):\n",
    "            # 上边\n",
    "            if plate[0][i] == \".\" and check(0,i,1):\n",
    "                ans.append([0,i])\n",
    "            # 下边\n",
    "            if plate[m-1][i] == \".\" and check(m-1,i,3):\n",
    "                ans.append([m-1,i])\n",
    "        for j in range(1,m-1):\n",
    "            # 左边\n",
    "            if plate[j][0] == \".\" and check(j,0,0):\n",
    "                ans.append([j,0])\n",
    "            # 右边\n",
    "            if plate[j][n-1] == \".\" and check(j,n-1,2):\n",
    "                ans.append([j,n-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    DR_LEFT = 0\n",
    "    DR_UP = 1\n",
    "    DR_RIGHT = 2\n",
    "    DR_DOWN = 3\n",
    "\n",
    "    DRS = [(0, 1), (-1, 0), (0, -1), (1, 0)]\n",
    "\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        n, m = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x, y, direction):\n",
    "            rest = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if rest == 0:\n",
    "                    return False\n",
    "\n",
    "                # 逆时针\n",
    "                # left->up, up->right, right->down, down->left\n",
    "                if plate[x][y] == 'W':\n",
    "                    direction = (direction + 1) % 4\n",
    "                # 顺时针\n",
    "                # left->down, down->right, right->up, up->left\n",
    "                elif plate[x][y] == 'E':\n",
    "                    direction = (direction + 3) % 4\n",
    "                x, y = x + self.DRS[direction][0], y + self.DRS[direction][1]\n",
    "                if not (0 <= x < n and 0 <= y < m):\n",
    "                    return False\n",
    "                rest -= 1\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(1, n - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, self.DR_LEFT):\n",
    "                ans.append([i, 0])\n",
    "            if plate[i][m - 1] == '.' and check(i, m - 1, self.DR_RIGHT):\n",
    "                ans.append([i, m - 1])\n",
    "\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[0][i] == '.' and check(0, i, self.DR_DOWN):\n",
    "                ans.append([0, i])\n",
    "            if plate[n - 1][i] == '.' and check(n - 1, i, self.DR_UP):\n",
    "                ans.append([n - 1, i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "D = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m = len(plate)\n",
    "        n = len(plate[0])\n",
    "\n",
    "        def check(i, j, d):\n",
    "            if plate[i][j] != '.':\n",
    "                return False\n",
    "\n",
    "            t = num + 1\n",
    "            while t > 0 and 0 <= i < m and 0 <= j < n:\n",
    "                if plate[i][j] == 'O':\n",
    "                    return True\n",
    "                elif plate[i][j] == 'W':\n",
    "                    d = (d - 1) % 4\n",
    "                elif plate[i][j] == 'E':\n",
    "                    d = (d + 1) % 4\n",
    "\n",
    "                di, dj = D[d]\n",
    "                i += di\n",
    "                j += dj\n",
    "                \n",
    "                t -= 1\n",
    "\n",
    "            return False\n",
    "\n",
    "        ret = []\n",
    "        for i in range(1, m - 1):\n",
    "            if check(i, 0, 0):\n",
    "                ret.append((i, 0))\n",
    "            if check(i, n - 1, 2):\n",
    "                ret.append((i, n - 1))\n",
    "\n",
    "        for j in range(1, n - 1):\n",
    "            if check(0, j, 1):\n",
    "                ret.append((0, j))\n",
    "            if check(m - 1, j, 3):\n",
    "                ret.append((m - 1, j))\n",
    "\n",
    "        return ret\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dir = [[0 , 1] , [1 , 0] , [0 , -1] , [-1 , 0]]\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m , n = len(plate) , len(plate[0])\n",
    "\n",
    "        def check(x:int , y:int , d:int) -> bool:\n",
    "            res = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if res == 0:\n",
    "                    return False\n",
    "                if plate[x][y] == 'E':\n",
    "                    d = (d + 1) % 4\n",
    "                elif plate[x][y] == 'W':\n",
    "                    d = (d + 3) % 4\n",
    "                x += dir[d][0]\n",
    "                y += dir[d][1]\n",
    "                if not(0 <= x < m and 0 <= y < n):\n",
    "                    return False\n",
    "                res -= 1\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "        for j in range(1 , n - 1):\n",
    "            if plate[0][j] == '.' and check(0 , j , 1):\n",
    "                ans.append([0 , j])\n",
    "            if plate[-1][j] == '.' and check(m - 1 , j , 3):\n",
    "                ans.append([m - 1 , j])\n",
    "        for j in range(1 , m - 1):\n",
    "            if plate[j][0] == '.' and check(j , 0 , 0):\n",
    "                ans.append([j , 0])\n",
    "            if plate[j][-1] == '.' and check(j , n - 1 , 2):\n",
    "                ans.append([j , n - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): \n",
    "                ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): \n",
    "                ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): \n",
    "                ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): \n",
    "                ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        row, col = len(plate), len(plate[0])\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        ans = []\n",
    "\n",
    "        def check(x, y, d):\n",
    "            cur_x, cur_y = x, y\n",
    "            for _ in range(num):\n",
    "                dx, dy = directions[d]\n",
    "                nxt_x, nxt_y = cur_x + dx, cur_y + dy\n",
    "                if not (0 <= nxt_x < row and 0 <= nxt_y < col):\n",
    "                    return False\n",
    "                if plate[nxt_x][nxt_y] == 'O':\n",
    "                    return True\n",
    "                if plate[nxt_x][nxt_y] == 'E':\n",
    "                    d = (d + 1) % 4\n",
    "                if plate[nxt_x][nxt_y] == 'W':\n",
    "                    d = (d - 1) % 4\n",
    "                cur_x, cur_y = nxt_x, nxt_y\n",
    "            return False\n",
    "\n",
    "        for j in range(1, col - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 2):\n",
    "                ans.append([0, j])\n",
    "            if plate[row - 1][j] == '.' and check(row - 1, j, 0):\n",
    "                ans.append([row - 1, j])\n",
    "        for i in range(1, row - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 1):\n",
    "                ans.append([i, 0])\n",
    "            if plate[i][col - 1] == '.' and check(i, col - 1, 3):\n",
    "                ans.append([i, col - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = ((0,1),(1,0),(0,-1),(-1,0))\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        row , column = len(plate) , len(plate[0])\n",
    "        ans = []\n",
    "        def check(x,y):\n",
    "            if(plate[x][y]!=\".\"):\n",
    "                return False\n",
    "            num1 = num\n",
    "            d = -1\n",
    "            if(y==0):\n",
    "                d = 0\n",
    "            if(y==column-1):\n",
    "                d = 2\n",
    "            if(x==0):\n",
    "                d = 1\n",
    "            if(x==row-1):\n",
    "                d = 3\n",
    "            while(plate[x][y]!='O'):\n",
    "                x+=direction[d][0]\n",
    "                y+=direction[d][1]\n",
    "                if(x<0 or x>=row or y<0 or y>=column):\n",
    "                    return False\n",
    "                if(plate[x][y]=='E'):\n",
    "                    d=(d+1)%4\n",
    "                if(plate[x][y]=='W'):\n",
    "                    d=(d+3)%4\n",
    "                num1 -= 1\n",
    "                if(num1<0):\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(1,row-1):\n",
    "            if check(i,0):\n",
    "                ans.append([i,0])\n",
    "            if check(i,column-1):\n",
    "                ans.append([i,column-1])\n",
    "        for j in range(1,column-1):\n",
    "            if check(0,j):\n",
    "                ans.append([0,j])\n",
    "            if check(row-1,j):\n",
    "                ans.append([row-1,j])\n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\r\n",
    "        m, n = len(plate), len(plate[0])\r\n",
    "\r\n",
    "        def check(x: int, y: int, d: int) -> bool:\r\n",
    "            left = num\r\n",
    "            while plate[x][y] != 'O':\r\n",
    "                if left == 0: return False  # 无剩余步数\r\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\r\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\r\n",
    "                x += DIRS[d][0]\r\n",
    "                y += DIRS[d][1]\r\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\r\n",
    "                left -= 1\r\n",
    "            return True\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for j in range(1, n - 1):\r\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\r\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\r\n",
    "        for i in range(1, m - 1):\r\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\r\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef dfs(self, location: list[int], plate: list[str], moving: str, nowsteep: int, maxsteep: int) -> bool:\n",
    "\t\t# location[i,j]位于i行j列\n",
    "\t\tif nowsteep >= maxsteep:\n",
    "\t\t\treturn False\n",
    "\t\tnowsteep += 1\n",
    "\t\tN = len(plate)  # N行\n",
    "\t\tM = len(plate[0])  # M列\n",
    "\t\tif moving == 'up':\n",
    "\t\t\tlocation[0] -= 1\n",
    "\t\t\tif location[0] < 0: return False  # 出界或\n",
    "\t\telif moving == 'down':\n",
    "\t\t\tlocation[0] += 1\n",
    "\t\t\tif location[0] >= N: return False\n",
    "\t\telif moving == 'r':\n",
    "\t\t\tlocation[1] += 1\n",
    "\t\t\tif location[1] >= M: return False\n",
    "\t\telse:\n",
    "\t\t\tlocation[1] -= 1\n",
    "\t\t\tif location[1] < 0: return False\n",
    "\t\tif plate[location[0]][location[1]] == 'O':  # 进洞\n",
    "\t\t\treturn True\n",
    "\t\telse:\n",
    "\t\t\tchar = plate[location[0]][location[1]]\n",
    "\t\t\tdicW = {'up': 'l', 'r': 'up', 'down': 'r', 'l': 'down'}\n",
    "\t\t\tdicE = {'up': 'r', 'r': 'down', 'down': 'l', 'l': 'up'}\n",
    "\t\t\tif char == 'W':\n",
    "\t\t\t\tmoving=dicW[moving]\n",
    "\t\t\tif char == 'E':\n",
    "\t\t\t\tmoving=dicE[moving]\n",
    "\t\t\treturn self.dfs(location, plate, moving, nowsteep, maxsteep)\n",
    "\n",
    "\tdef ballGame(self, num: int, plate: list[str]) -> list[list[int]]:\n",
    "\t\tans = []\n",
    "\t\tN = len(plate)  # N行\n",
    "\t\tM = len(plate[0])  # M列\n",
    "\t\ts = set()\n",
    "\t\ts = ((0, 0), (0, M - 1), (N - 1, 0), (N - 1, M - 1))\n",
    "\t\tfor beginI in range(N):\n",
    "\t\t\tfor beginJ in range(M):\n",
    "\t\t\t\tif (beginI == 0 or beginI == N - 1 or beginJ == 0 or beginJ == M - 1) and (beginI, beginJ) not in s:\n",
    "\t\t\t\t\tm = 'dwqf'  # 确定方向进行dfs\n",
    "\t\t\t\t\tif beginI == 0:\n",
    "\t\t\t\t\t\tm = 'down'\n",
    "\t\t\t\t\tif beginI == N - 1:\n",
    "\t\t\t\t\t\tm = 'up'\n",
    "\t\t\t\t\tif beginJ == 0:\n",
    "\t\t\t\t\t\tm = 'r'\n",
    "\t\t\t\t\tif beginJ == M - 1:\n",
    "\t\t\t\t\t\tm = 'l'\n",
    "\t\t\t\t\tif plate[beginI][beginJ]=='.':\n",
    "\t\t\t\t\t\tflag = self.dfs([beginI, beginJ], plate, m, 0, num)\n",
    "\t\t\t\t\t\tif flag:\n",
    "\t\t\t\t\t\t\tans.append([beginI, beginJ])\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        row,col = len(plate),len(plate[0])\n",
    "        DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "        def check(x,y,d):\n",
    "            nonlocal DIRS\n",
    "            remain = num\n",
    "            while plate[x][y]!='O':\n",
    "                if remain==0: return False\n",
    "                if plate[x][y] == 'W': d = (d+3)%4\n",
    "                elif plate[x][y] == 'E': d = (d+1)%4\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0<=x<row and 0<=y<col):\n",
    "                    return False\n",
    "                remain -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1,col-1):\n",
    "            if plate[0][j]=='.' and check(0,j,1): ans.append([0,j])\n",
    "            if plate[-1][j]=='.' and check(row-1, j, 3): ans.append([row-1,j])\n",
    "        for i in range(1,row-1):\n",
    "            if plate[i][0]=='.' and check(i, 0, 0): ans.append([i,0])\n",
    "            if plate[i][-1]=='.' and check(i, col-1, 2): ans.append([i,col-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        n = len(plate)\n",
    "        m = len(plate[0])\n",
    "        #       >   v    <   ^\n",
    "        #   E : -1     W : +1\n",
    "        rot = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        que = []\n",
    "        ans = []\n",
    "        '''\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if plate[i][j] == \"O\":\n",
    "                    for _ in range(4):\n",
    "                        que.append([i,j,0,_])\n",
    "        while que:\n",
    "            nowX,nowY,nowCount,nowD = que.pop(0)\n",
    "            nowD = nowD%4\n",
    "            if nowCount > num:\n",
    "                continue\n",
    "            if nowX<0 or nowX>=n or nowY<0 or nowY>=m:\n",
    "                continue\n",
    "            elif (nowX==0 and nowD==3) or (nowX==n-1 and nowD==1) or (nowY==0 and nowD==2) or (nowY==m-1 and nowD==0):\n",
    "                if plate[nowX][nowY] == \".\" and not((nowX==0 or nowX==n-1) and (nowY==0 or nowY==m-1)):\n",
    "                    ans.append([nowX,nowY])\n",
    "                    continue\n",
    "            if plate[nowX][nowY] ==\"E\":\n",
    "                temp = [nowX+rot[nowD-1][0],nowY+rot[nowD-1][1]]\n",
    "                que.append([temp[0], temp[1], nowCount+1, nowD-1])\n",
    "            elif plate[nowX][nowY] ==\"W\":\n",
    "                temp = [nowX + rot[(nowD + 1)%4][0], nowY + rot[(nowD + 1)%4][1]]\n",
    "                que.append([temp[0], temp[1], nowCount + 1, nowD + 1])\n",
    "            else:\n",
    "                temp = [nowX + rot[nowD][0], nowY + rot[nowD][1]]\n",
    "                que.append([temp[0], temp[1], nowCount + 1, nowD])\n",
    "            try:\n",
    "                if plate[temp[0]][temp[1]] ==\"O\":\n",
    "                    que.pop(-1)\n",
    "            except:\n",
    "                pass\n",
    "\n",
    "        return ans\n",
    "        '''\n",
    "        def check(x,y,dir):\n",
    "            count = 0\n",
    "            while True:\n",
    "                if count > num:\n",
    "                    return False\n",
    "                if plate[x][y] ==\"E\":\n",
    "                    dir = (dir + 1)%4\n",
    "                elif plate[x][y] ==\"W\":\n",
    "                    dir = (dir - 1)%4\n",
    "                x,y = x+rot[dir][0] , y+rot[dir][1]\n",
    "                count += 1\n",
    "                if x<0 or x>=n or y<0 or y>=m:\n",
    "                    return False\n",
    "                elif plate[x][y] ==\"O\" and count <= num:\n",
    "                    return True\n",
    "        for i in range(1,m-1):\n",
    "            if plate[0][i] == \".\" and check(0,i,1)==True:\n",
    "                ans.append([0,i])\n",
    "            if plate[n-1][i] == \".\" and check(n-1, i, 3) == True:\n",
    "                ans.append([n-1, i])\n",
    "        for i in range(1, n - 1):\n",
    "            if plate[i][0] == \".\" and check(i, 0, 0) == True:\n",
    "                ans.append([i, 0])\n",
    "            if plate[i][m-1] == \".\" and check(i, m-1, 2) == True:\n",
    "                ans.append([i, m-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Right, Down, Left, Up\n",
    "        N, M = len(plate), len(plate[0])\n",
    "        result = []\n",
    "        \n",
    "        def is_valid_position(x, y):\n",
    "            return 0 <= x < N and 0 <= y < M\n",
    "        \n",
    "        def simulate(x, y, direction):\n",
    "            for step in range(num):\n",
    "                x, y = x + directions[direction][0], y + directions[direction][1]\n",
    "                # If the ball goes out of bounds, return False\n",
    "                if not is_valid_position(x, y):\n",
    "                    return False\n",
    "                if plate[x][y] == 'O':\n",
    "                    return True\n",
    "                if plate[x][y] == 'W':\n",
    "                    direction = (direction - 1) % 4\n",
    "                elif plate[x][y] == 'E':\n",
    "                    direction = (direction + 1) % 4\n",
    "            return False\n",
    "        \n",
    "        # Check top and bottom rows, excluding corners\n",
    "        for col in range(1, M - 1):\n",
    "            if plate[0][col] == '.' and simulate(0, col, 1):\n",
    "                result.append([0, col])\n",
    "            if plate[N - 1][col] == '.' and simulate(N - 1, col, 3):\n",
    "                result.append([N - 1, col])\n",
    "\n",
    "        # Check left and right columns, excluding corners\n",
    "        for row in range(1, N - 1):\n",
    "            if plate[row][0] == '.' and simulate(row, 0, 0):\n",
    "                result.append([row, 0])\n",
    "            if plate[row][M - 1] == '.' and simulate(row, M - 1, 2):\n",
    "                result.append([row, M - 1])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        ans = []\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j, dt):\n",
    "            q = deque([(i, j, dt, num)])\n",
    "            vis = set()\n",
    "            vis.add((i, j, dt))\n",
    "            while q:\n",
    "                i, j, dt, left = q.popleft()\n",
    "                if plate[i][j] == 'O':\n",
    "                    return True\n",
    "                if plate[i][j] == 'W': dt = (dt + 3) % 4\n",
    "                if plate[i][j] == 'E': dt = (dt + 1) % 4\n",
    "                r, c = i + d[dt][0], j + d[dt][1]\n",
    "                if 0<=r<m and 0<=c<n and (r, c, dt) not in vis and left > 0:\n",
    "                    q.append((r, c, dt, left-1))\n",
    "                    vis.add((r, c, dt))\n",
    "            return False\n",
    "\n",
    "        for k in range(1, n - 1):\n",
    "            if plate[0][k] == '.' and f(0, k, 1): ans.append([0, k])\n",
    "            if plate[m-1][k] == '.' and f(m - 1, k, 3): ans.append([m - 1, k])\n",
    "        for p in range(1, m - 1):\n",
    "            if plate[p][0] == '.' and f(p, 0, 0): ans.append([p, 0])\n",
    "            if plate[p][n-1] == '.' and f(p, n - 1, 2): ans.append([p, n - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))  # 右下左上（顺时针）\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "\n",
    "        def check(x: int, y: int, d: int) -> bool:\n",
    "            left = num\n",
    "            while plate[x][y] != 'O':\n",
    "                if left == 0: return False  # 无剩余步数\n",
    "                if plate[x][y] == 'W':   d = (d + 3) % 4  # 逆时针\n",
    "                elif plate[x][y] == 'E': d = (d + 1) % 4  # 顺时针\n",
    "                x += DIRS[d][0]\n",
    "                y += DIRS[d][1]\n",
    "                if not (0 <= x < m and 0 <= y < n): return False  # 出界\n",
    "                left -= 1\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and check(0, j, 1): ans.append([0, j])  # 上边\n",
    "            if plate[-1][j] == '.' and check(m - 1, j, 3): ans.append([m - 1, j])  # 下边\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and check(i, 0, 0): ans.append([i, 0])  # 左边\n",
    "            if plate[i][-1] == '.' and check(i, n - 1, 2): ans.append([i, n - 1])  # 右边\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 四个方向用四个索引0，1，2，3表示，分别对应：向上、向左、向下、向右\n",
    "# 索引从小到大，表示上左下右的逆时针旋转，对应grid中的\"W\"\n",
    "# 索引从大变小，表示右下左上的顺时针旋转，对应grid中的\"E\"\n",
    "h_d = [(-1, 0), (0, -1), (1, 0),  (0, 1)]\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, x, y, d, num, grid):\n",
    "        if num == -1 or x == self.n or x == -1 or y == self.m or y == -1:\n",
    "            return False         \n",
    "        if grid[x][y] == \"O\":\n",
    "            return True\n",
    "        elif grid[x][y] == \"W\":     # 逆时针旋转，方向索引变大\n",
    "            d = (d+1) % 4\n",
    "        elif grid[x][y] == \"E\":     # 顺时针旋转，方向索引变小\n",
    "            d = (d-1) % 4\n",
    "        x, y = x + h_d[d][0], y + h_d[d][1]\n",
    "        return self.dfs(x, y, d, num-1, grid)\n",
    "        \n",
    "\n",
    "    def ballGame(self, num: int, grid: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        self.n, self.m = len(grid), len(grid[0])\n",
    "\n",
    "        for x in range(1, self.n-1):\n",
    "            # 从右边缘出发，方向应该向左，d = 1\n",
    "            if grid[x][self.m-1] == \".\" and self.dfs(x, self.m-1, 1, num, grid):\n",
    "                ans.append([x, self.m-1])\n",
    "            # 从左边缘出发，方向应该向右，d = 3\n",
    "            if grid[x][0] == \".\" and self.dfs(x, 0, 3, num, grid):\n",
    "                ans.append([x, 0])\n",
    "\n",
    "        for y in range(1, self.m-1):\n",
    "            # 从下边缘出发，方向应该向上，d = 0\n",
    "            if grid[self.n-1][y] == \".\" and self.dfs(self.n-1, y, 0, num, grid):\n",
    "                ans.append([self.n-1, y])\n",
    "            # 从上边缘出发，方向应该向下，d = 2\n",
    "            if grid[0][y] == \".\" and self.dfs(0, y, 2, num, grid):               \n",
    "                ans.append([0, y])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        \n",
    "        toward=[0,0]\n",
    "\n",
    "        row=len(plate)\n",
    "        col=len(plate[0])\n",
    "        ans=[]\n",
    "        maxstep=0\n",
    "        for x in [0,row-1]:\n",
    "            for y in range(1,col-1):\n",
    "               # print(\"x,y\")\n",
    "                #print(x,y)\n",
    "                if plate[x][y]==\".\":\n",
    "                    if x==0:\n",
    "                        a=1\n",
    "                        b=0\n",
    "                    else:\n",
    "                        a=-1\n",
    "                        b=0\n",
    "                    x1=x\n",
    "                    y1=y\n",
    "                    cnt=1\n",
    "                    f=0\n",
    "                   \n",
    "                    while 0<=x1<row and 0<=y1<col:\n",
    "                        if plate[x1][y1]==\"O\":\n",
    "                            f=1\n",
    "                            break\n",
    "                        elif plate[x1][y1]==\"E\":\n",
    "                            if b==0:\n",
    "                                a,b=-1*b,-1*a\n",
    "                            else:\n",
    "                                a,b=b,a\n",
    "                        elif plate[x1][y1]==\"W\":\n",
    "                            if b==0:\n",
    "                                a,b=b,a\n",
    "                            else:\n",
    "                                a,b=-1*b,-1*a\n",
    "                        if cnt>num:\n",
    "                            break\n",
    "                        #print(\"ab\")\n",
    "                        #print(a,b)\n",
    "                        x1=x1+a\n",
    "                        y1=y1+b\n",
    "                        cnt=cnt+1\n",
    "                    if f==1 :\n",
    "                        ans.append([x,y])\n",
    "        \n",
    "        for y in [0,col-1]:\n",
    "            for x in range(1,row-1):\n",
    "                \n",
    "                if plate[x][y]==\".\":\n",
    "                    if y==0:\n",
    "                        a=0\n",
    "                        b=1\n",
    "                    else:\n",
    "                        a=0\n",
    "                        b=-1\n",
    "                    x1=x\n",
    "                    y1=y\n",
    "                    cnt=1\n",
    "                    f=0\n",
    "                    while 0<=x1<row and 0<=y1<col:\n",
    "                        if plate[x1][y1]==\"O\":\n",
    "                            f=1\n",
    "                            break\n",
    "                        elif plate[x1][y1]==\"E\":\n",
    "                            if b==0:\n",
    "                                a,b=-1*b,-1*a\n",
    "                            else:\n",
    "                                a,b=b,a\n",
    "                        elif plate[x1][y1]==\"W\":\n",
    "                            if b==0:\n",
    "                                a,b=b,a\n",
    "                            else:\n",
    "                                a,b=-1*b,-1*a\n",
    "                        if cnt>num:\n",
    "                            break\n",
    "                        x1=x1+a\n",
    "                        y1=y1+b\n",
    "                        cnt=cnt+1\n",
    "                        \n",
    "                    if f==1 :\n",
    "                        ans.append([x,y])\n",
    "         \n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        def check(i, j, d):\n",
    "            k = num\n",
    "            while plate[i][j] != 'O':\n",
    "                if k == 0:\n",
    "                    return False\n",
    "                if plate[i][j] == 'W':\n",
    "                    d = (d+3) % 4\n",
    "                elif plate[i][j] == 'E':\n",
    "                    d = (d+1) % 4\n",
    "                i, j = i + dirs[d], j + dirs[d+1]\n",
    "                if not (0 <= i < m and 0 <= j < n):\n",
    "                    return False \n",
    "                k -= 1\n",
    "            return True\n",
    "\n",
    "        \n",
    "        dirs = (0,1,0,-1,0)\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        ans = []\n",
    "        for i in range(1,m-1):\n",
    "            if plate[i][0] == '.' and check(i,0,0):\n",
    "                ans.append([i,0])\n",
    "            if plate[i][n-1] == '.' and check(i,n-1,2):\n",
    "                ans.append([i,n-1])\n",
    "        for j in range(1,n-1):\n",
    "            if plate[0][j] == '.' and check(0,j,1):\n",
    "                ans.append([0,j])\n",
    "            if plate[m-1][j] == '.' and check(m-1,j,3):\n",
    "                ans.append([m-1,j])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        d=[(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        m=len(plate)\n",
    "        n=len(plate[0])\n",
    "        ans=[]\n",
    "        for i in range(1,n-1):\n",
    "            x,y=0,i\n",
    "            xx,yy=0,i \n",
    "            di=1\n",
    "            cc=-1\n",
    "            while cc<num:\n",
    "                cc+=1\n",
    "                if x<0 or y<0 or x>=m or y>=n:\n",
    "                    break\n",
    "                if plate[x][y]!=\".\" and cc==0:\n",
    "                    break\n",
    "                if plate[x][y]==\"O\":\n",
    "                    ans.append([xx,yy])\n",
    "                    break\n",
    "                if plate[x][y]==\"E\":\n",
    "                    di=(di+1)%4\n",
    "                elif plate[x][y]=='W':\n",
    "                    di=(di+3)%4\n",
    "                x+=d[di][0]\n",
    "                y+=d[di][1]\n",
    "        for i in range(1,n-1):\n",
    "            x,y=m-1,i\n",
    "            xx,yy=m-1,i \n",
    "            di=3\n",
    "            cc=-1\n",
    "            while cc<num:\n",
    "                cc+=1\n",
    "                if x<0 or y<0 or x>=m or y>=n:\n",
    "                    break\n",
    "                if plate[x][y]!=\".\" and cc==0:\n",
    "                    break\n",
    "                if plate[x][y]==\"O\":\n",
    "                    ans.append([xx,yy])\n",
    "                    break\n",
    "                if plate[x][y]==\"E\":\n",
    "                    di=(di+1)%4\n",
    "                elif plate[x][y]=='W':\n",
    "                    di=(di+3)%4\n",
    "                x+=d[di][0]\n",
    "                y+=d[di][1]\n",
    "        for i in range(1,m-1):\n",
    "            x,y=i,0\n",
    "            xx,yy=i,0\n",
    "            di=0\n",
    "            cc=-1\n",
    "            print(xx,yy,\"------\")\n",
    "            while cc<num:\n",
    "                cc+=1\n",
    "                print(x,y)\n",
    "                if x<0 or y<0 or x>=m or y>=n:\n",
    "                    break\n",
    "                if plate[x][y]!=\".\" and cc==0:\n",
    "                    break\n",
    "                if plate[x][y]==\"O\":\n",
    "                    ans.append([xx,yy])\n",
    "                    break\n",
    "                if plate[x][y]==\"E\":\n",
    "                    di=(di+1)%4\n",
    "                elif plate[x][y]=='W':\n",
    "                    di=(di+3)%4\n",
    "                x+=d[di][0]\n",
    "                y+=d[di][1]\n",
    "        for i in range(1,m-1):\n",
    "            x,y=i,n-1\n",
    "            xx,yy=i,n-1 \n",
    "            #print(xx,yy,plate[xx][yy])\n",
    "            di=2\n",
    "            cc=-1\n",
    "            while cc<num:\n",
    "                cc+=1\n",
    "                if x<0 or y<0 or x>=m or y>=n:\n",
    "                    break\n",
    "                if plate[x][y]!=\".\" and cc==0:\n",
    "                    break\n",
    "                if plate[x][y]==\"O\":\n",
    "                    ans.append([xx,yy])\n",
    "                    #print(ans)\n",
    "                    break\n",
    "                if plate[x][y]==\"E\":\n",
    "                    di=(di+1)%4\n",
    "                elif plate[x][y]=='W':\n",
    "                    di=(di+3)%4\n",
    "                x+=d[di][0]\n",
    "                y+=d[di][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m=len(plate)\n",
    "        n=len(plate[0])\n",
    "\n",
    "\n",
    "        x=deque([])\n",
    "        d1={(1,0):[0,-1],(0,-1):[-1,0],(-1,0):[0,1],(0,1):[1,0]}\n",
    "        d2={(1,0):[0,1],(0,1):[-1,0],(-1,0):[0,-1],(0,-1):[1,0]}\n",
    "        d=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        for j in range(1,n-1):\n",
    "            if plate[0][j]=='.':\n",
    "                x.append([0,j,0,'.',[1,0],[0,j]])\n",
    "            if plate[m-1][j]=='.':\n",
    "                x.append([m-1,j,0,'.',[-1,0],[m-1,j]])\n",
    "        for i in range(1,m-1):\n",
    "            if plate[i][0]=='.':\n",
    "                x.append([i,0,0,'.',[0,1],[i,0]])\n",
    "            if plate[i][n-1]=='.':\n",
    "                x.append([i,n-1,0,'.',[0,-1],[i,n-1]])\n",
    "\n",
    "        ans=[]\n",
    "        while(len(x)):\n",
    "            x0=x.popleft()\n",
    "            x5=x0\n",
    "            x0,x1,x2,x3,x4,x5=x0[0],x0[1],x0[2],x0[3],x0[4],x0[5]\n",
    "\n",
    "            #print(x5)\n",
    "            if plate[x0][x1]=='O' and x2<=num:\n",
    "                    ans.append(x5)\n",
    "            if x2==num+1:\n",
    "                break\n",
    "            elif x3=='E':\n",
    "                a0,b0=d1[tuple(x4)][0],d1[tuple(x4)][1]\n",
    "                a=x0+a0\n",
    "                b=x1+b0\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],[a0,b0],x5]) \n",
    "            \n",
    "            elif x3=='W':\n",
    "                a0,b0=d2[tuple(x4)][0],d2[tuple(x4)][1]\n",
    "                a=x0+a0\n",
    "                b=x1+b0\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],[a0,b0],x5]) \n",
    "                \n",
    "            elif x3=='.':\n",
    "                a=x0+x4[0]\n",
    "                b=x1+x4[1]\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],x4,x5]) \n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m=len(plate)\n",
    "        n=len(plate[0])\n",
    "\n",
    "\n",
    "        x=deque([])\n",
    "        d1={(1,0):[0,-1],(0,-1):[-1,0],(-1,0):[0,1],(0,1):[1,0]}\n",
    "        d2={(1,0):[0,1],(0,1):[-1,0],(-1,0):[0,-1],(0,-1):[1,0]}\n",
    "        d=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        for j in range(1,n-1):\n",
    "            if plate[0][j]=='.':\n",
    "                x.append([0,j,0,'.',[1,0],[0,j]])\n",
    "            if plate[m-1][j]=='.':\n",
    "                x.append([m-1,j,0,'.',[-1,0],[m-1,j]])\n",
    "        for i in range(1,m-1):\n",
    "            if plate[i][0]=='.':\n",
    "                x.append([i,0,0,'.',[0,1],[i,0]])\n",
    "            if plate[i][n-1]=='.':\n",
    "                x.append([i,n-1,0,'.',[0,-1],[i,n-1]])\n",
    "\n",
    "        ans=[]\n",
    "        while(len(x)):\n",
    "            x0=x.popleft()\n",
    "            x5=x0\n",
    "            x0,x1,x2,x3,x4,x5=x0[0],x0[1],x0[2],x0[3],x0[4],x0[5]\n",
    "            if plate[x0][x1]=='O' and x2<=num:\n",
    "                    ans.append(x5)\n",
    "            if x2==num+1:\n",
    "                break\n",
    "            elif x3=='E':\n",
    "                a0,b0=d1[tuple(x4)][0],d1[tuple(x4)][1]\n",
    "                a=x0+a0\n",
    "                b=x1+b0\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],[a0,b0],x5]) \n",
    "            \n",
    "            elif x3=='W':\n",
    "                a0,b0=d2[tuple(x4)][0],d2[tuple(x4)][1]\n",
    "                a=x0+a0\n",
    "                b=x1+b0\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],[a0,b0],x5]) \n",
    "                \n",
    "            elif x3=='.':\n",
    "                a=x0+x4[0]\n",
    "                b=x1+x4[1]\n",
    "                if a<0 or a>m-1 or b<0 or b>n-1:\n",
    "                    continue \n",
    "                x.append([a,b,x2+1,plate[a][b],x4,x5]) \n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 顺时针：E\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        dq = deque()\n",
    "        for i in range(1, m-1):\n",
    "            if plate[i][0] == \".\": dq.append((i, 0, 0, num))\n",
    "            if plate[i][n-1] == \".\": dq.append((i, n-1, 2,num))\n",
    "        for i in range(1, n-1):\n",
    "            if plate[0][i] == \".\": dq.append((0, i, 1, num))\n",
    "            if plate[m-1][i]== \".\": dq.append((m-1, i, 3, num))\n",
    "        ans = []\n",
    "        for x, y, di, t in dq:\n",
    "            sx, sy = x, y\n",
    "            while t >= 0:\n",
    "                if plate[x][y] == \"O\":\n",
    "                    ans.append([sx, sy])\n",
    "                    break\n",
    "                if plate[x][y] == \"W\": di = (di + 3) % 4\n",
    "                if plate[x][y] == \"E\": di = (di + 1) % 4\n",
    "                dx, dy = d[di]\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n: x, y, t = nx, ny, t-1\n",
    "                else: break\n",
    "\n",
    "        return sorted(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "\n",
    "        def gs(x,y,d):\n",
    "            return x + y * 1000 + d * 1000000 \n",
    "        vis = defaultdict(int) \n",
    "        n, m = len(plate), len(plate[0])\n",
    "        Q = [] \n",
    "        dir_xy = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        for i in range(1,n-1):\n",
    "            if plate[i][0] == '.':\n",
    "                Q.append((i,0,i,0, 1, 0))\n",
    "            if plate[i][m-1] == '.':\n",
    "                Q.append((i,m-1,i,m-1,3,0))\n",
    "        for j in range(1,m-1):\n",
    "            if plate[0][j] == '.':\n",
    "                Q.append((0, j, 0, j,2, 0))\n",
    "            if plate[n-1][j] == '.':\n",
    "                Q.append((n-1, j,n-1, j, 0, 0))\n",
    "\n",
    "        ans = set()\n",
    "        while Q:\n",
    "            x,y,px, py, d,step = Q.pop(0)\n",
    "\n",
    "            if step>num:\n",
    "                continue \n",
    "            \n",
    "            if plate[x][y] == 'O':\n",
    "                ans.add((px, py))\n",
    "                continue \n",
    "\n",
    "            if plate[x][y] == 'E':\n",
    "                d = (d+1)%4\n",
    "            elif plate[x][y] == 'W':\n",
    "                d = (d-1)%4\n",
    "            \n",
    "            nx, ny = x + dir_xy[d][0], y + dir_xy[d][1] \n",
    "\n",
    "            if 0<=nx < n and 0<=ny<m:\n",
    "                stat_ = gs(nx,ny,d)\n",
    "                if not vis[stat_]:\n",
    "                    vis[stat_] = 1\n",
    "                    Q.append((nx,ny,px, py,d,step+1))\n",
    "        \n",
    "        return list(ans) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.f = {}\n",
    "        self.dx = [0, 1, 0, -1]\n",
    "        self.dy = [1, 0, -1, 0]\n",
    "    \n",
    "    def dfs(self, x, y, d, p, n, m):\n",
    "        if (x, y, d) in self.f:\n",
    "            return self.f[(x, y, d)]\n",
    "        \n",
    "        if p[x][y] == 'O':\n",
    "            return 1\n",
    "        \n",
    "        d1 = d\n",
    "        if p[x][y] == 'E':\n",
    "            d1 = (d + 1) % 4\n",
    "        elif p[x][y] == 'W':\n",
    "            d1 = (d + 3) % 4\n",
    "        \n",
    "        a, b = x + self.dx[d1], y + self.dy[d1]\n",
    "        \n",
    "        if a < 0 or b < 0 or a >= n or b >= m:\n",
    "            return 10 ** 7\n",
    "        \n",
    "        self.f[(x, y, d)] = 1 + self.dfs(a, b, d1, p, n, m)\n",
    "        return self.f[(x, y, d)]\n",
    "\n",
    "    def ballGame(self, num, pp):\n",
    "        n, m = len(pp), len(pp[0])\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(1, m - 1):\n",
    "            if pp[0][i] == '.' and self.dfs(0, i, 1, pp, n, m) <= num + 1:\n",
    "                ans.append([0, i])\n",
    "\n",
    "        for i in range(1, m - 1):\n",
    "            if pp[n - 1][i] == '.' and self.dfs(n - 1, i, 3, pp, n, m) <= num + 1:\n",
    "                ans.append([n - 1, i])\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if pp[i][0] == '.' and self.dfs(i, 0, 0, pp, n, m) <= num + 1:\n",
    "                ans.append([i, 0])\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            if pp[i][m - 1] == '.' and self.dfs(i, m - 1, 2, pp, n, m) <= num + 1:\n",
    "                ans.append([i, m - 1])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        def g(i,j,c,r):\n",
    "          res=False\n",
    "          if plate[i][j] =='O':\n",
    "              return True\n",
    "          if r==0:\n",
    "              return False    \n",
    "          if plate[i][j] =='W':\n",
    "              c=(c-1)%4\n",
    "          if plate[i][j] =='E':\n",
    "              c=(c+1)%4\n",
    "          x=i+d[c][0]\n",
    "          y=j+d[c][1]\n",
    "          if 0<=x<n and 0<=y<m:\n",
    "              res=g(x,y,c,r-1)\n",
    "          return res\n",
    "        ans=[]\n",
    "        n,m=len(plate),len(plate[0])  \n",
    "        d=[[-1,0],[0,1],[1,0],[0,-1]]  \n",
    "        for i in range(1,n-1):\n",
    "            if plate[i][0]=='.':\n",
    "               if g(i,0,1,num)==True:\n",
    "                   ans.append([i,0])\n",
    "            if plate[i][-1]=='.':\n",
    "               if g(i,m-1,3,num)==True:\n",
    "                   ans.append([i,m-1])\n",
    "        for j in range(1,m-1):\n",
    "            if plate[0][j]=='.':\n",
    "               if g(0,j,2,num):\n",
    "                   ans.append([0,j])\n",
    "            if plate[n-1][j]=='.':\n",
    "               if g(n-1,j,0,num)==True:\n",
    "                   ans.append([n-1,j])\n",
    "                               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        #num可以行走的步数  plate一个二维数组\n",
    "        r,c=len(plate),len(plate[0])\n",
    "        \n",
    "        def walk(i_,j_,d_,num_):# i_,j_ 坐标,d_方向,num_步数\n",
    "            if num_==0:\n",
    "                if plate[i_][j_]==\"O\":return True\n",
    "                else:return False\n",
    "            if i_<0 or i_>r-1 or j_<0 or j_>c-1:\n",
    "                    return False\n",
    "            if num_>0:\n",
    "                cur = plate[i_][j_]\n",
    "                if cur==\".\":#空白\n",
    "                    i_+=d_[0]\n",
    "                    j_+=d_[1]\n",
    "                    return walk(i_,j_,d_,num_-1)\n",
    "                if cur==\"W\":#逆时针\n",
    "                    d_1=[d_[1]*(-1),d_[0]]\n",
    "                    i_+=d_1[0]\n",
    "                    j_+=d_1[1]\n",
    "                    return walk(i_,j_,d_1,num_-1)\n",
    "                if cur==\"E\":#顺时针\n",
    "                    # print(d_)\n",
    "                    d_1=[d_[1],d_[0]*(-1)]\n",
    "                    i_+=d_1[0]\n",
    "                    j_+=d_1[1]\n",
    "                    return walk(i_,j_,d_1,num_-1)\n",
    "                if cur==\"O\":return True\n",
    "        res=[]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if plate[i][j]!=\".\":continue\n",
    "                if i==0:\n",
    "                    if j==0 or j==c-1:continue\n",
    "                    if walk(i,j,[1,0],num):\n",
    "                        res.append([i,j])\n",
    "                if i==r-1:\n",
    "                    if j==0 or j==c-1:continue\n",
    "                    if walk(i,j,[-1,0],num):\n",
    "                        res.append([i,j])\n",
    "                if j==0:\n",
    "                    if i==0 or i==r-1:continue\n",
    "                    if walk(i,j,[0,1],num):\n",
    "                        res.append([i,j])\n",
    "                if j==c-1:\n",
    "                    if i==0 or i==r-1:continue\n",
    "                    if walk(i,j,[0,-1],num):\n",
    "                        res.append([i,j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        #num可以行走的步数  plate一个二维数组\n",
    "        r,c=len(plate),len(plate[0])\n",
    "        \n",
    "        def walk(i_,j_,d_,num_):# i_,j_ 坐标,d_方向,num_步数\n",
    "            if num_==0:\n",
    "                if plate[i_][j_]==\"O\":return True\n",
    "                else:return False\n",
    "            if i_<0 or i_>r-1 or j_<0 or j_>c-1:\n",
    "                    return False\n",
    "            if num_>0:\n",
    "                cur = plate[i_][j_]\n",
    "                if cur==\".\":#空白\n",
    "                    i_+=d_[0]\n",
    "                    j_+=d_[1]\n",
    "                    return walk(i_,j_,d_,num_-1)\n",
    "                if cur==\"W\":#逆时针\n",
    "                    d_1=[d_[1]*(-1),d_[0]]\n",
    "                    i_+=d_1[0]\n",
    "                    j_+=d_1[1]\n",
    "                    return walk(i_,j_,d_1,num_-1)\n",
    "                if cur==\"E\":#顺时针\n",
    "                    # print(d_)\n",
    "                    d_1=[d_[1],d_[0]*(-1)]\n",
    "                    i_+=d_1[0]\n",
    "                    j_+=d_1[1]\n",
    "                    return walk(i_,j_,d_1,num_-1)\n",
    "                if cur==\"O\":return True\n",
    "        res=[]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if plate[i][j]!=\".\":continue\n",
    "                if i==0:\n",
    "                    if j==0 or j==c-1:continue\n",
    "                    if walk(i,j,[1,0],num):\n",
    "                        res.append([i,j])\n",
    "                if i==r-1:\n",
    "                    if j==0 or j==c-1:continue\n",
    "                    if walk(i,j,[-1,0],num):\n",
    "                        res.append([i,j])\n",
    "                if j==0:\n",
    "                    if i==0 or i==r-1:continue\n",
    "                    if walk(i,j,[0,1],num):\n",
    "                        res.append([i,j])\n",
    "                if j==c-1:\n",
    "                    if i==0 or i==r-1:continue\n",
    "                    if walk(i,j,[0,-1],num):\n",
    "                        res.append([i,j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        m, n = len(plate), len(plate[0])\n",
    "        ans = []\n",
    "        def dfs(i, j, x, y):\n",
    "            for _ in range(num):\n",
    "                i += x\n",
    "                j += y\n",
    "                if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                    return False\n",
    "                if plate[i][j] == '.':\n",
    "                    continue\n",
    "                if plate[i][j] == 'O':\n",
    "                    return True\n",
    "                if plate[i][j] == 'E':\n",
    "                    return dfs(i, j, y, -x) \n",
    "                if plate[i][j] == 'W':\n",
    "                    return dfs(i, j, -y, x)\n",
    "            return False\n",
    "\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.': \n",
    "                if dfs(i, 0, 0, 1):\n",
    "                    ans.append([i, 0])\n",
    "            if plate[i][n - 1] == '.':\n",
    "                if dfs(i, n - 1, 0, -1):\n",
    "                    ans.append([i, n - 1])\n",
    "        for i in range(1, n - 1):\n",
    "            if plate[0][i] == '.':\n",
    "                if dfs(0, i, 1, 0):\n",
    "                    ans.append([0, i])\n",
    "            if plate[m - 1][i] == '.':\n",
    "                if dfs(m - 1, i, -1, 0):\n",
    "                    ans.append([m - 1, i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        next_direcions = {(-1, 0):{'W':(0, -1), 'E':(0, 1)},\n",
    "                          (1, 0):{'W':(0, 1), 'E':(0, -1)},\n",
    "                          (0, -1):{'W':(1, 0), 'E':(-1, 0)},\n",
    "                          (0, 1):{'W':(-1, 0), 'E':(1, 0)}\n",
    "                          }\n",
    "        seen = {}\n",
    "        def dfs(i, j, direction, num_left):\n",
    "            if i<0 or j<0 or i>=len(plate) or j>=len(plate[0]):\n",
    "                return False\n",
    "            if plate[i][j] == 'O':\n",
    "                #seen[(i, j, direction)] = num_left\n",
    "                return True\n",
    "            if num_left<=0:\n",
    "                #seen[(i, j, direction)] = float('i')\n",
    "                return False\n",
    "            # if (i, j, direction) in seen:\n",
    "            #     if \n",
    "            #     return seen[(i, j, direction)]\n",
    "            if plate[i][j] == '.':\n",
    "                dx, dy = direction\n",
    "            else:\n",
    "                dx, dy = next_direcions[direction][plate[i][j]]\n",
    "            i, j = i+dx, j+dy\n",
    "            ans = dfs(i, j, (dx, dy), num_left-1)\n",
    "            #seen[(i, j, direction)] = ans\n",
    "            return ans\n",
    "        ans = []\n",
    "        for j in range(1, len(plate[0])-1):\n",
    "            if plate[0][j]=='.' and dfs(0, j, (1, 0), num):\n",
    "                ans.append([0, j])\n",
    "            if plate[-1][j]=='.' and dfs(len(plate)-1, j, (-1, 0), num):\n",
    "                ans.append([len(plate)-1, j])\n",
    "        for i in range(1, len(plate)-1):\n",
    "            if plate[i][0]=='.' and dfs(i, 0, (0, 1), num):\n",
    "                ans.append([i, 0])\n",
    "            if plate[i][-1]=='.' and dfs(i, len(plate[0])-1, (0, -1), num):\n",
    "                ans.append([i, len(plate[0])-1])\n",
    "        return ans\n",
    "        \n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        # 回字形进洞, 1000*1000 , 不会超过10**6个格子\n",
    "        # \".....\",\n",
    "        # \"....O\",\n",
    "        # \"....O\",\n",
    "        # \".....\"\n",
    "        ##############\n",
    "        # \"W.W.WE..\",\n",
    "        # \".WWWEW..\",\n",
    "        # \"EWW.WE.E\",\n",
    "        # \"E.W.E.E.\",\n",
    "        # \".OEOO.EO\",\n",
    "        # \"WE.WOE.W\",\n",
    "        # \"WW...E..\",  --6\n",
    "        # \".WEWO..O\",\n",
    "        # \"E....E..\",\n",
    "        # \".OWE....\"\n",
    "\n",
    "        m,n=len(plate),len(plate[0])\n",
    "        dix=[(1,0),(0,-1),(-1,0),(0,1)]\n",
    "        res=[]\n",
    "        def dfs(i,j,di,dis):\n",
    "            # print(i,j,di,dis)\n",
    "            if not dis>0:\n",
    "                return False\n",
    "            if not m>i>=0<=j<n:\n",
    "                return False\n",
    "            # if i in [0,m-1] or j in [0,n-1]:\n",
    "            #     return False or plate[i][j]=='O' # 边缘擦边WO\n",
    "            if plate[i][j]=='.':\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            elif plate[i][j]=='O':\n",
    "                return True\n",
    "            elif plate[i][j]=='E':\n",
    "                di=(di+1)%4\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            else:\n",
    "                di=(di-1+4)%4\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            return dfs(xx,yy,di,dis-1)\n",
    "\n",
    "        for i in range(1,m-1):\n",
    "            # plate[i][0]\n",
    "            # plate[i][n-1]\n",
    "            di=3\n",
    "            if plate[i][0]=='.' and dfs(i+dix[di][0],0+dix[di][1],di,num):\n",
    "                res.append([i,0])\n",
    "            di=1\n",
    "            if plate[i][n-1]=='.' and dfs(i+dix[di][0],n-1+dix[di][1],di,num):\n",
    "                res.append([i,n-1])\n",
    "        for i in range(1,n-1):\n",
    "            # plate[0][i]\n",
    "            # plate[m-1][i]\n",
    "            di=0\n",
    "            if plate[0][i]=='.' and dfs(0+dix[di][0],i+dix[di][1],di,num):\n",
    "                res.append([0,i])\n",
    "            di=2\n",
    "            if plate[m-1][i]=='.' and dfs(m-1+dix[di][0],i+dix[di][1],di,num):\n",
    "                res.append([m-1,i])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        # 回字形进洞, 1000*1000 , 不会超过10**6个格子\n",
    "        # \".....\",\n",
    "        # \"....O\",\n",
    "        # \"....O\",\n",
    "        # \".....\"\n",
    "        ##############\n",
    "        # \"W.W.WE..\",\n",
    "        # \".WWWEW..\",\n",
    "        # \"EWW.WE.E\",\n",
    "        # \"E.W.E.E.\",\n",
    "        # \".OEOO.EO\",\n",
    "        # \"WE.WOE.W\",\n",
    "        # \"WW...E..\",  --6\n",
    "        # \".WEWO..O\",\n",
    "        # \"E....E..\",\n",
    "        # \".OWE....\"\n",
    "\n",
    "        m,n=len(plate),len(plate[0])\n",
    "        dix=[(1,0),(0,-1),(-1,0),(0,1)]\n",
    "        res=[]\n",
    "        def dfs(i,j,di,dis):\n",
    "            # print(i,j,di,dis)\n",
    "            if not dis>0:\n",
    "                return False\n",
    "            if not m>i>=0<=j<n:\n",
    "                return False\n",
    "            # if i in [0,m-1] or j in [0,n-1]:\n",
    "            #     return False or plate[i][j]=='O' # 边缘擦边WO\n",
    "            if plate[i][j]=='.':\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            elif plate[i][j]=='O':\n",
    "                return True\n",
    "            elif plate[i][j]=='E':\n",
    "                di=(di+1)%4\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            else:\n",
    "                di=(di-1+4)%4\n",
    "                dx,dy=dix[di]\n",
    "                xx,yy=i+dx,j+dy\n",
    "            return dfs(xx,yy,di,dis-1)\n",
    "\n",
    "        for i in range(1,m-1):\n",
    "            # plate[i][0]\n",
    "            # plate[i][n-1]\n",
    "            di=3\n",
    "            if plate[i][0]=='.' and dfs(i+dix[di][0],0+dix[di][1],di,num):\n",
    "                res.append([i,0])\n",
    "            di=1\n",
    "            if plate[i][n-1]=='.' and dfs(i+dix[di][0],n-1+dix[di][1],di,num):\n",
    "                res.append([i,n-1])\n",
    "        for i in range(1,n-1):\n",
    "            # plate[0][i]\n",
    "            # plate[m-1][i]\n",
    "            di=0\n",
    "            if plate[0][i]=='.' and dfs(0+dix[di][0],i+dix[di][1],di,num):\n",
    "                res.append([0,i])\n",
    "            di=2\n",
    "            if plate[m-1][i]=='.' and dfs(m-1+dix[di][0],i+dix[di][1],di,num):\n",
    "                res.append([m-1,i])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        dirs=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        m=len(plate)\n",
    "        n=len(plate[0])\n",
    "        def dfs(x:int , y:int, predir:int, tmpnum:int):\n",
    "            if plate[x][y]=='O' and tmpnum<=num:\n",
    "                return True\n",
    "            if tmpnum>=num:\n",
    "                return False\n",
    "            if plate[x][y]=='.':\n",
    "                nextdir=predir\n",
    "            elif plate[x][y]=='E':\n",
    "                nextdir=(predir+1)%4\n",
    "            else:\n",
    "                nextdir=(predir+3)%4\n",
    "\n",
    "            tmpx = x + dirs[nextdir][0]\n",
    "            tmpy = y + dirs[nextdir][1]\n",
    "            if tmpx<0 or tmpx>=m or tmpy<0 or tmpy>=n:\n",
    "                return False\n",
    "            return dfs(tmpx, tmpy, nextdir, tmpnum+1)\n",
    "\n",
    "        res=[]\n",
    "        for i in range(1, n-1):\n",
    "            if plate[0][i]=='.' and dfs(0, i, 1, 0):\n",
    "                res.append([0,i])\n",
    "            if plate[m-1][i]=='.' and dfs(m-1, i, 3, 0):\n",
    "                res.append([m-1, i])\n",
    "        for i in range(1,m-1):\n",
    "            if plate[i][0]=='.' and dfs(i, 0, 0, 0):\n",
    "                res.append([i, 0])\n",
    "            if plate[i][n-1]=='.' and dfs(i, n-1, 2, 0):\n",
    "                res.append([i, n-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        holes = []\n",
    "        m = len(plate)\n",
    "        n = len(plate[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if plate[i][j] == 'O':\n",
    "                    holes.append((i, j))\n",
    "\n",
    "        clock_turn = {(1, 0): (0, -1), (0, -1): (-1, 0), (-1, 0): (0, 1), (0, 1): (1, 0)}\n",
    "        conter_turn = {(0, -1): (1, 0), (-1, 0): (0, -1), (0, 1): (-1, 0), (1, 0): (0, 1)}\n",
    "\n",
    "        def dfs(direction, step_remain, plate, i, j):\n",
    "            if step_remain < 0:\n",
    "                return False\n",
    "\n",
    "            if 0 <= i < m and 0 <= j < n:\n",
    "                if plate[i][j] == 'O':\n",
    "                    return True\n",
    "                \n",
    "                if plate[i][j] == 'W':\n",
    "                    next_dire = conter_turn[direction]\n",
    "                elif plate[i][j] == 'E':\n",
    "                    next_dire = clock_turn[direction]\n",
    "                else:\n",
    "                    next_dire = direction\n",
    "                \n",
    "                next_i = i + next_dire[0]\n",
    "                next_j = j + next_dire[1]\n",
    "\n",
    "                return dfs(next_dire, step_remain - 1, plate, next_i, next_j)\n",
    "\n",
    "            return False\n",
    "        \n",
    "        res = []\n",
    "        for i in range(1, m - 1):\n",
    "            if plate[i][0] == '.' and dfs((0, 1), num, plate, i, 0):\n",
    "                res.append([i, 0])\n",
    "\n",
    "            if plate[i][n - 1] == '.' and dfs((0, -1), num, plate, i, n - 1):\n",
    "                res.append([i, n - 1])\n",
    "        \n",
    "        for j in range(1, n - 1):\n",
    "            if plate[0][j] == '.' and dfs((1, 0), num, plate, 0, j):\n",
    "                res.append([0, j])\n",
    "            if plate[m - 1][j] == '.' and dfs((-1, 0), num, plate, m - 1, j):\n",
    "                res.append([m - 1, j])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        @cache\n",
    "        def g(i,j,c,r):\n",
    "          res=False\n",
    "          if plate[i][j] =='O':\n",
    "              return True\n",
    "          if r==0:\n",
    "              return False    \n",
    "          if plate[i][j] =='W':\n",
    "              c=(c-1)%4\n",
    "          if plate[i][j] =='E':\n",
    "              c=(c+1)%4\n",
    "          x=i+d[c][0]\n",
    "          y=j+d[c][1]\n",
    "          if 0<=x<n and 0<=y<m:\n",
    "              res=g(x,y,c,r-1)\n",
    "          return res\n",
    "        ans=[]\n",
    "        n,m=len(plate),len(plate[0])  \n",
    "        d=[[-1,0],[0,1],[1,0],[0,-1]]  \n",
    "        for i in range(1,n-1):\n",
    "            if plate[i][0]=='.':\n",
    "               if g(i,0,1,num)==True:\n",
    "                   ans.append([i,0])\n",
    "            if plate[i][-1]=='.':\n",
    "               if g(i,m-1,3,num)==True:\n",
    "                   ans.append([i,m-1])\n",
    "        for j in range(1,m-1):\n",
    "            if plate[0][j]=='.':\n",
    "               if g(0,j,2,num):\n",
    "                   ans.append([0,j])\n",
    "            if plate[n-1][j]=='.':\n",
    "               if g(n-1,j,0,num)==True:\n",
    "                   ans.append([n-1,j])\n",
    "                               \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        # 0左 1上 2右 3下\n",
    "        m=len(plate)\n",
    "        n=len(plate[0])\n",
    "        steps=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "        def ok(x, y):\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                return True\n",
    "            return False\n",
    "        st_list=[]\n",
    "        for i in range(m):\n",
    "            if i==0 or i==m-1:\n",
    "                continue\n",
    "            if plate[i][0]=='.': \n",
    "                st_list.append((i,0,2, num))\n",
    "            if plate[i][n-1]=='.':\n",
    "                st_list.append((i,n-1,0, num))\n",
    "        for j in range(n):\n",
    "            if j==0 or j==n-1:\n",
    "                continue\n",
    "            if plate[0][j]=='.': \n",
    "                st_list.append((0,j,3, num))\n",
    "            if plate[m-1][j]=='.':\n",
    "                st_list.append((m-1,j,1, num))\n",
    "        mark=[[[False for _ in range(4)] for _ in range(n)] for _ in range(m)]\n",
    "        ans=[]\n",
    "        for st in st_list:\n",
    "            dq=deque()\n",
    "            dq.append(st)\n",
    "            while dq:\n",
    "                i,j,direct,tmp_num=dq.popleft()\n",
    "                if plate[i][j]=='O':\n",
    "                    ans.append([st[0],st[1]])\n",
    "                    break\n",
    "                ni=i+steps[direct][0]\n",
    "                nj=j+steps[direct][1]\n",
    "                tmp_num-=1\n",
    "                if tmp_num<0:\n",
    "                    continue\n",
    "                if ok(ni, nj):\n",
    "                    if plate[ni][nj]=='E': \n",
    "                        direct=(direct+1)%4\n",
    "                    elif plate[ni][nj]=='W': \n",
    "                        direct=direct-1\n",
    "                        if direct==-1:\n",
    "                            direct=3\n",
    "                    if mark[ni][nj][direct] is False:\n",
    "                        mark[ni][nj][direct]=True\n",
    "                        dq.append((ni, nj, direct, tmp_num))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def ballGame(self, num: int, plate: List[str]) -> List[List[int]]:\n",
    "        def trigger(i,j, direction,all_position):\n",
    "            if plate[i][j]=='.':\n",
    "                while True:\n",
    "                    stack.append([i,j,direction])\n",
    "                    dp_direct[direction][i][j] = True\n",
    "                    flag, new_i,new_j = self.justice_direction(n, m, i, j, direction)\n",
    "                    if flag:\n",
    "                        i,j = new_i,new_j\n",
    "                        direction = self.change_direction(plate[i][j], direction)\n",
    "                        if direction!=-1 and not dp_direct[direction][i][j]:\n",
    "                            continue\n",
    "                        elif direction==-1:\n",
    "                            step = 0\n",
    "                            dp_step[0][i][j] = 0\n",
    "                            dp_step[1][i][j] = 0\n",
    "                            dp_step[2][i][j] = 0\n",
    "                            dp_step[3][i][j] = 0\n",
    "                        else:\n",
    "                            step = dp_step[direction][i][j]\n",
    "                    else:\n",
    "                        step = num+1\n",
    "\n",
    "                    while(len(stack)>0):\n",
    "                        step+=1\n",
    "                        i,j,direction = stack.pop()\n",
    "                        dp_step[direction][i][j] = step\n",
    "                    break\n",
    "                \n",
    "                if dp_step[direction][i][j]<=num:\n",
    "                    all_position.append([i,j])\n",
    "        \n",
    "        n = len(plate)\n",
    "        m = len(plate[0])\n",
    "        dp_direct = [[[False for _ in range(m)] for _ in range(n)] for _ in range(4)]\n",
    "        dp_step =   [[[num+1 for _ in range(m)] for _ in range(n)] for _ in range(4)]\n",
    "        stack = []\n",
    "\n",
    "        all_position = []\n",
    "        for i in range(1, n-1):\n",
    "            direction = 1\n",
    "            j = 0\n",
    "            step = trigger(i,j, direction,all_position)\n",
    "\n",
    "        for j in range(1, m-1):\n",
    "            direction = 0\n",
    "            i=n-1\n",
    "            step = trigger(i,j, direction,all_position)\n",
    "\n",
    "        for i in range(1, n-1):\n",
    "            direction = 3\n",
    "            j=m-1\n",
    "            step = trigger(i,j, direction,all_position)\n",
    "\n",
    "        for j in range(1, m-1):\n",
    "            direction = 2\n",
    "            i=0\n",
    "            step = trigger(i,j, direction,all_position)\n",
    "\n",
    "        return all_position\n",
    "                \n",
    "    def justice_direction(self, n, m, i, j, direction):\n",
    "        if direction==0:\n",
    "            return i-1>=0, i-1, j\n",
    "        elif direction==1:\n",
    "            return j+1<m, i, j+1\n",
    "        elif direction==2:\n",
    "            return i+1<n, i+1, j\n",
    "        elif direction==3:\n",
    "            return j-1>=0, i, j-1\n",
    "        else:\n",
    "            raise ValueError(direction)\n",
    "\n",
    "    def change_direction(self, c, direction):\n",
    "        if c=='.':\n",
    "            return direction\n",
    "        elif c=='E':\n",
    "            return (direction+1)%4\n",
    "        elif c=='W':\n",
    "            return (direction-1)%4\n",
    "        elif c=='O':\n",
    "            return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
